I suggest looking at the "free" tools Bethesda offers for their games, or particularly the Obsidian variant for Fallout:NV, as they are built around making very large numbers of dynamic conversion trees for NPCs and quests.
A dialog in most current RPGs consists of sequences of scripted conversion interspersed with dialog options. Selecting an option plays another sequence. A sequence could include: text spoken, audio, cutscenes, or game actions.
The actual dialog points are just a list of options. The options may have requirements: you might only be able to threaten an NPC if you have a high Strength, or only be able to say "I know who you are, let us talk" if you've reached a certain dialog point with another NPC. Each option will then direct the user to another sequence or another dialog.
The whole conversion is a graph. Yes, a graph, not a tree - there are likely multiple dialog choices that can lead into the same direction eventually, so a tree is a poor choice. The "enter" node is often an initial "hello, good day" sequence that then leads into the opening dialog options, while other times it jumps right into dialog options.
The structure of a Conversion then is a graph of nodes, where each node is either an Action (play cutscene, run Lua script, etc.) or a Dialog (a list of options).
If you were writing this in a Java-esque OOP style, you'd probably have a Conversation containing a dictionary of node names to INode objects and derived ActionNode and DialogNode classes. The ActionNode would contain a List of IAction objects like a CutsceneAction, SetQuestStateAction, ScriptAction, or GotoNodeAction. The DialogNode would contain a List of Option objects, where an Option has a script or somesuch for calculating requirements and then the name of the conversion node to enter when the option is chosen. This is probably the easiest way to think of things as a human, though it's a rather poor way to structure code.
A procedural approach would probably just use a Lua script to represent the whole thing. Such a script would have a function for each node and available procedures to perform actions, build dialog option lists, queue up animations and speech, etc.
An approach I'd prefer is a hybrid of the two. You want custom data structures and conversion code that innately understands as much about what a conversion is, how the graph works, how you can move between nodes, and so on, because you want to build nice tools for designers to create and test conversations. A raw script makes that difficult. However, you don't want to build a bloated over-engineered Java-style class hierarchy for every simple problem. A smaller flat DSL-like VM to execute conversations directly while still having enough metadata for editing and tool-supported verification works nicely. This is a relatively difficult option to engineer, though.
The tools support item is one of the trickier ones. If you build much logic into scripts, tools will not be able to reason about what the script will do. If you don't use scripts, you have to re-engineer a lot of the features you can pull off with scripts. A good balance is likely to add the ability to do all your most common actions without script but still allow script for complicated rare cases. That way, you tools and verification code can at least handle most of the conversations, and you only need technically-savvy designers and extensive manual testing for a small subset of conversations.
